package com.zhugang.week09;

/**
 * @program algorithms
 * @description: canReach
 * @author: chanzhugang
 * @create: 2022/08/23 20:43
 */
public class CanReach {

    /**
     * 1306 跳跃游戏III
     * 图上的搜索问题
     *
     * @param arr
     * @param start
     * @return
     */
    private boolean[] visited;
    private boolean reached = false;

    public boolean canReach(int[] arr, int start) {
        // start是下标， 每次跳 i + arr[i] 或者 i - arr[i], 是否能到达值为0的下标
        // 看着不像其实是DFS, 画出来就是一个图
        visited = new boolean[arr.length];
        dfs(arr, start);
        return reached;
    }

    private void dfs(int[] arr, int curi) {
        if (reached) {
            return;
        }
        if (arr[curi] == 0) {
            reached = true;
            return;
        }
        visited[curi] = true;

        int move2Left = curi - arr[curi];
        if (move2Left >= 0 && move2Left < arr.length && visited[move2Left] == false) {
            dfs(arr, move2Left);
        }

        int move2Right = curi + arr[curi];
        if (move2Right >= 0 && move2Right < arr.length && visited[move2Right] == false) {
            dfs(arr, move2Right);
        }
    }
}